'''
https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/
'''

MAXN = 150001
tree = [[0] * 26 for _ in range(MAXN)]
ended = [False] * MAXN
cnt = 1
# 静态空间实现
class WordDictionary:

    def __init__(self):
        global cnt, tree, ended
        for i in range(1, cnt + 1):
            tree[i] = [0] * 26
        ended[1:cnt+1] = [False] * cnt
        cnt = 1

    def addWord(self, word: str) -> None:
        global cnt, tree, ended
        cur = 1
        for c in word:
            path = ord(c) - ord('a')
            if not tree[cur][path]:
                cnt += 1
                tree[cur][path] = cnt
            cur = tree[cur][path]
        ended[cur] = True

    def search(self, word: str) -> bool:
        global cnt, tree, ended
        n = len(word)
        def dfs(root, i):
            if i == n: return ended[root]
            if word[i] == '.':
                for path in range(26):
                    if tree[root][path]:
                        if dfs(tree[root][path], i + 1):
                            return True
                return False
            else:
                path = ord(word[i]) - ord('a')
                if not tree[root][path]: return False
                return dfs(tree[root][path], i + 1)
        return dfs(1, 0)


class Node():
    def __init__(self):
        self.ended = False
        self.children = {}

class WordDictionary2:

    def __init__(self):
        self.root = Node()

    def addWord(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = Node()
            cur = cur.children[c]
        cur.ended = True

    def search(self, word: str) -> bool:
        n = len(word)
        def dfs(root, i):
            if i == n: return root.ended
            if word[i] == '.':
                for next in root.children.values():
                    if dfs(next, i + 1):
                        return True
                return False
            else:
                if word[i] in root.children:
                    return dfs(root.children[word[i]], i + 1)
                return False
        return dfs(self.root, 0)


